package 数据结构和算法.剑指offer.树.从上到下打印二叉树Ⅱ;

import 数据结构和算法.数据结构.普通二叉树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从上到下打印二叉树Ⅱ
 * <p>
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。*
 * <p>
 * 仿照上题的思路，我们这回还是使用BFS来进行遍历，唯一不同的是我们需要使用队列存储当前层的结果并打印
 */

public class Test {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (null == root) {
            return null;
        }

        List<List<Integer>> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (null != queue) {
            List<Integer> temp = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (null != node.getLeftTreeNode()) {
                    queue.add(node.getLeftTreeNode());
                }
                if (null != node.getRightTreeNode()) {
                    queue.add(node.getRightTreeNode());
                }

                temp.add(node.getValue());
            }

            resList.add(temp);
        }

        return resList;
    }
}
